package me.algo.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author guozheng
 * @date 2024/4/18
 */
public class T7 {
    public static void main(String[] args) {

    }


    /**
     * 236. 二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        List<TreeNode> pplist = findParentList(root, p);
        List<TreeNode> qplist = findParentList(root, q);
        TreeNode dp = null;
        for (int i = 0; i < pplist.size() && i < qplist.size(); i++) {
            if (pplist.get(i).val == qplist.get(i).val) {
                dp = pplist.get(i);
            }
        }
        return dp;
    }

    private static List<TreeNode> findParentList(TreeNode root, TreeNode p) {
        LinkedList<Pair> que = new LinkedList<>();
        que.addLast(new Pair(root, new ArrayList<>()));
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                size--;
                Pair pair = que.removeFirst();
                TreeNode node = pair.node;
                if (node.val == p.val) {
                    List<TreeNode> rtn = new ArrayList<>(pair.pList);
                    rtn.add(node);
                    return rtn;
                }
                if (node.left != null) {
                    List<TreeNode> np = new ArrayList<>(pair.pList);
                    np.add(node);
                    que.add(new Pair(node.left, np));
                }
                if (node.right != null) {
                    List<TreeNode> np = new ArrayList<>(pair.pList);
                    np.add(node);
                    que.add(new Pair(node.right, np));
                }
            }
        }
        return new ArrayList<>();
    }


    record Pair(TreeNode node, List<TreeNode> pList) {

    }

}
